/*
 Problem Description
Hogwarts正式开学以后,Harry发现在Hogwarts里,某些楼梯并不是静止不动的，相反,他们每隔一分钟就变动一次方向. 
比如下面的例子里,一开始楼梯在竖直方向,一分钟以后它移动到了水平方向,再过一分钟它又回到了竖直方向.Harry发现对他来说很难找到能使得他最快到达目的地的路线,这时Ron(Harry最好的朋友)告诉Harry正好有一个魔法道具可以帮助他寻找这样的路线,而那个魔法道具上的咒语,正是由你纂写的. 

 

Input
测试数据有多组，每组的表述如下：
第一行有两个数,M和N,接下来是一个M行N列的地图,'*'表示障碍物,'.'表示走廊,'|'或者'-'表示一个楼梯,并且标明了它在一开始时所处的位置:'|'表示的楼梯在最开始是竖直方向,'-'表示的楼梯在一开始是水平方向.地图中还有一个'S'是起点,'T'是目标,0<=M,N<=20,地图中不会出现两个相连的梯子.Harry每秒只能停留在'.'或'S'和'T'所标记的格子内.

 

Output
只有一行,包含一个数T,表示到达目标的最短时间. 
注意:Harry只能每次走到相邻的格子而不能斜走,每移动一次恰好为一分钟,并且Harry登上楼梯并经过楼梯到达对面的整个过程只需要一分钟,Harry从来不在楼梯上停留.并且每次楼梯都恰好在Harry移动完毕以后才改变方向.

 

Sample Input
5 5
**..T
**.*.
..|..
.*.*.
S....
 
5 5
**..T
**.*.
..|..
.*.*.
S...-
Sample Output
7


 */
package com.yuan.algorithms.acm201506;

import java.util.Scanner;

class Node3{
	int x;
	int y;
	int time;//以用时间
	int direction;//方向
	
	public Node3(int x, int y, int time, int direction) {
		this.x = x;
		this.y = y;
		this.time = time;
		this.direction = direction;
	}
}
public class HD1180诡异的楼梯 {

	static char[][] map;
	static int[][] mark;
	static int[] start;
	static int[] end;
	static final int[] var= {0, 1, 1, 0, 0, -1, -1, 0};
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()) {
			int m = sc.nextInt();
			int n = sc.nextInt();
			map = new char[n][m];
			mark = new int[n][m];
			start = new int[2];
			end = new int[2];
			for (int i = 0; i < m; i++) {
				String t = sc.next();
				for (int j = 0; j < n; j++) {
					char a = t.charAt(j);
					map[j][i] = a;
					if (a=='S') {
						start[0] = j;
						start[1] = i;
					}else if (a=='T') {
						end[0] = j;
						end[1] = i;
					}
				}
			}
			int time = bfs(start[0], start[1], 0, 0);
			System.out.println(time);
		}
	}
	
	private static int bfs(int x, int y, int time, int direction) throws Exception {
		Queue3 queue = new Queue3();
		Node3 origin = new Node3(x, y, time, direction);
		queue.add(origin);
		while(!queue.isEmpty()) {
			Node3 temp = (Node3)queue.poll();
			
			//找到终点
			if (map[temp.x][temp.y] == 'T') {
				return temp.time;
			}
			for (int i = 0; i < 4; i++) {
				int newX = temp.x+var[i*2];
				int newY = temp.y+var[i*2+1];
				//判断下标是否越界
				boolean indexJudge = (newX>=0 && newX<map.length) && (newY>=0 && newY<map[0].length);
				if (!indexJudge) {
					continue;
				}
				//如果进入过该地区，则舍弃
				if (mark[newX][newY] == 1) {
					continue;
				}
				//判断该位置是否可以通过
				boolean mapJudge = map[newX][newY] == '.' || map[newX][newY] == 'S' || map[newX][newY] == 'T';
				if (mapJudge) {
					queue.add(new Node3(newX, newY, temp.time+1, i));
					mark[temp.x][temp.y] = 1; //标记已探索当前地区
				}else if (map[newX][newY] == '-') {
					if (temp.direction == 1) {
						if (newX+1 <map.length) {
							queue.add(new Node3(newX+1, newY, temp.time+1, i));
						}
					}else if (temp.direction == 3) {
						if (newX-1>=0) {
							queue.add(new Node3(newX-1, newY, temp.time+1, i));
						}
					}
				}else if (map[newX][newY] == '|') {
					if (temp.direction == 0) {
						if (newY+1<map[0].length)
							queue.add(new Node3(newX, newY+1, temp.time+1, i));
					}else if (temp.direction == 2) {
						if (newY-1>=0)
							queue.add(new Node3(newX, newY-1, temp.time+1, i));
					}
				}
			}
		}
		return 0;
	}

}


/*
 * 循环数组实现队列
 */
class Queue3 {
	
	private static final int CAP = 10;// 队列默认大小
	private Object[] elements;// 数据元素数组
	private int capacity;// 数组的大小
	private int front;// 队首指针
	private int rear;// 队尾指针
	
	public Queue3() {
		this(CAP);
	}
	
	public Queue3(int cap) {
		capacity = cap + 1;// 数组长度加1，用于区分队列满的情况
		elements = new Object[capacity];
		front = rear = 0;
	}
	
	/**
	 * 返回队列大小
	 * 
	 * @return
	 */
	public int getSize() {
		return (rear - front + capacity) % capacity;
	}
	
	/**
	 * 判断队列是否为空
	 * 
	 * @return
	 */
	public boolean isEmpty() {
		return front == rear;
	}
	
	/**
	 * 向队列添加数据
	 * 
	 * @param e
	 */
	public void add(Object e) {
		// 判断队列是否存满了
		if (getSize() == capacity - 1) {
			expandSpace();// 扩展队列
		}
		elements[rear] = e;
		rear = (rear + 1) % capacity;
	}
	
	/**
	 * 扩展队列容量
	 */
	private void expandSpace() {
		Object[] temp = new Object[elements.length * 2 - 1];// 数组容量增大一倍
		int i = front;
		int j = 0;
		// 将从front开始到rear前一个存储单元的元素复制到新数组
		while (i != rear) {
			temp[j++] = elements[i];
			i = (i + 1) % capacity;
		}
		elements = temp;
		capacity = elements.length;
		front = 0;
		rear = j;// 设置新的队尾指针
	}
	
	/**
	 * 队首元素出队
	 * 
	 * @return
	 * @throws Exception
	 */
	public Object poll() throws Exception {
		if (isEmpty()) {
			throw new Exception("错误：队列为空");
		}
		Object obj = elements[front];
		elements[front] = null;// 删除原来的数据
		front = (front + 1) % capacity;// 更新队首指针
		return obj;
	}
	
	/**
	 * 取队首元素（不删除元素）
	 * 
	 * @return
	 * @throws Exception
	 */
	public Object peek() throws Exception {
		if (isEmpty()) {
			throw new Exception("错误：队列为空");
		}
		return elements[front];
	}
}
